package cn.whdream.datastructure.tree.threadedbinarytree;


public class ThreadedBinaryTreeDemo {
	public static void main(String[] args) {
		//测试一把中序线索二叉树的功能
				HeroNode root = new HeroNode(1, "tom");
				HeroNode node2 = new HeroNode(3, "jack");
				HeroNode node3 = new HeroNode(6, "smith");
				HeroNode node4 = new HeroNode(8, "mary");
				HeroNode node5 = new HeroNode(10, "king");
				HeroNode node6 = new HeroNode(14, "dim");
				
				//二叉树，后面我们要递归创建, 现在简单处理使用手动创建
				root.setLeft(node2);
				root.setRight(node3);
				node2.setLeft(node4);
				node2.setRight(node5);
				node3.setLeft(node6);
				
				//测试中序线索化
				ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
				threadedBinaryTree.setRoot(root);
				System.out.println("前序顺序打印");
				threadedBinaryTree.preOrder();
				System.out.println("中序线索化");
				threadedBinaryTree.threadedNodes();
				System.out.println("打印中序线索化");
				threadedBinaryTree.printThreadedNodesInfixList();
				//TODO  调研一下 线索化后 前序遍历，中序遍历应用场景和意义
//				System.out.println("前序线索化");
//				threadedBinaryTree.threadedNodesByPreOrder();
				//测试:1,3,8,10,6,14
//				HeroNode cur = node4;
//				HeroNode leftNode = cur.getLeft();
//				HeroNode rightNode = cur.getRight();
//				System.out.println(cur.no+"号结点的前驱结点是 ="  + leftNode +"type:"+cur.leftType); //3
//				System.out.println(cur.no+"号结点的后继结点是="  + rightNode+"type:"+cur.leftType); //1
	}
	/**
	 * 
	 * @author admin
	 * 实现线索化的二叉树
	 */
	private static class ThreadedBinaryTree {
		private HeroNode root;
		private HeroNode pre;
		
		
		public void setRoot(HeroNode root) {
			this.root = root;
		}
		/**
		 * TODO 研究一下其内部整体一个思路，在前序遍历和后序遍历的实践
		 */
		public void printThreadedNodesInfixList() {
			HeroNode node = root;
			while (node != null) {
				while (node.getLeftType() == 0) {
					node = node.getLeft();
				}
				System.out.println(node);
				if (node.getRightType() == 1) {
					node = node.right;
					System.out.println(node);
				}
				node = node.getRight();
			}
		}

		public void threadedNodes() {
			threadedNodes(root);
			
		}
		public void threadedNodesByPreOrder() {
			threadedNodesByPreOrder(root);
		}
		

		/**
		 *  此为以中序遍历为例	
		 * @param node
		 */
		private void threadedNodes(HeroNode node) {
			if (node == null) {
				return;
			}
			threadedNodes(node.left);
			//以8为例，此时左边是为空的，且pre也是为空的；所以 8的前置节点虽然进入了，但是前置节点为0
			if (node.left == null) {
				System.out.println(node);
				node.left = pre;
				node.leftType = 1;
				System.out.println("此时pre"+pre);
			}
			
			if (pre != null && pre.right == null ) {
				pre.setRight(node);
				pre.rightType = 1;
			}
			pre = node;
			threadedNodes(node.right);
		}
		/**
		 * 1,3,8,10,6,14
		 * @param node
		 */
		private void threadedNodesByPreOrder(HeroNode node) {
			if (node == null) {
				return;
			}
			//以8为例，此时左边是为空的，且pre也是为空的；所以 8的前置节点虽然进入了，但是前置节点为0
			if (node.left == null) {
				System.out.println(node);
				node.left = pre;
				node.leftType = 1;
				System.out.println("此时pre"+pre);
			}
			
			if (pre != null && pre.right == null ) {
				pre.setRight(node);
				pre.rightType = 1;
			}
			pre = node;
			threadedNodes(node.left);
			threadedNodes(node.right);
		}

		//删除结点
		public void delNode(int no) {
			if(root != null) {
				//如果只有一个root结点, 这里立即判断root是不是就是要删除结点
				if(root.no == no) {
					root = null;
				} else {
					//递归删除
					root.delNode(no);
				}
			}else{
				System.out.println("空树，不能删除~");
			}
		}
		//前序遍历
		public void preOrder() {
			if(this.root != null) {
				this.root.preOrder();
			}else {
				System.out.println("二叉树为空，无法遍历");
			}
		}
		
		//中序遍历
		public void infixOrder() {
			if(this.root != null) {
				this.root.infixOrder();
			}else {
				System.out.println("二叉树为空，无法遍历");
			}
		}
		//后序遍历
		public void postOrder() {
			if(this.root != null) {
				this.root.postOrder();
			}else {
				System.out.println("二叉树为空，无法遍历");
			}
		}
		
		//前序遍历
		public HeroNode preOrderSearch(int no) {
			if(root != null) {
				return root.preOrderSearch(no);
			} else {
				return null;
			}
		}
		//中序遍历
		public HeroNode infixOrderSearch(int no) {
			if(root != null) {
				return root.infixOrderSearch(no);
			}else {
				return null;
			}
		}
		//后序遍历
		public HeroNode postOrderSearch(int no) {
			if(root != null) {
				return this.root.postOrderSearch(no);
			}else {
				return null;
			}
		}
	}
	private static class HeroNode{
		private String name;
		private int no;
		private HeroNode left;
		private HeroNode right;
		//说明
		//1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
		//2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点
		private int leftType;
		private int rightType;
		
		public int getLeftType() {
			return leftType;
		}
		public void setLeftType(int leftType) {
			this.leftType = leftType;
		}
		public int getRightType() {
			return rightType;
		}
		public void setRightType(int rightType) {
			this.rightType = rightType;
		}
		public HeroNode( int no,String name) {
			super();
			this.name = name;
			this.no = no;
		}
		/**
		 * 	叶子结点 直接删除
		 *     非叶子结点，直接删除该子数
		 * @param no2 指定的结点号
		 */
		public HeroNode delNode(int no2) {
			HeroNode result;
			if(this.left != null && this.left.no == no2) {
				result = this.left;
				this.left = null;
				return result;
			}
			if(this.right != null && this.right.no == no2) {
				result = this.right;
				this.right = null;
				return result;
			}
			if (this.left != null) {
				return left.delNode(no2);
			}
			if (this.right != null) {
				return right.delNode(no2);
			}
			return null;
		}

		public HeroNode postOrderSearch(int no2) {
			System.out.println("进入后序遍历");
			if (left != null) {
				if (left.postOrderSearch(no2) != null) {
					return left.postOrderSearch(no2);
				}
			}
			
			if (right != null) {
				if (right.postOrderSearch(no2) != null) {
					return right.postOrderSearch(no2);
				}
			}
			
			if (this.no == no2) {
				return this;
			}else {
				return null;
			}
			
		}

		public HeroNode infixOrderSearch(int no2) {
			System.out.println("进入中序遍历");
			if (left != null) {
				if (left.infixOrderSearch(no2) != null) {
					return left.infixOrderSearch(no2);
				}
			}
			if (this.no == no2) {
				return this;
			}
			if (right != null) {
				if (right.infixOrderSearch(no2) != null) {
					return right.infixOrderSearch(no2);
				}
			}
			return null;
		}

		public HeroNode preOrderSearch(int no2) {
			System.out.println("进入前序遍历");
			if (this.no == no2) {
				return this;
			}
			if (left != null) {
				if (left.preOrderSearch(no2) != null) {
					return left.preOrderSearch(no2);
				}
			}
			if (right != null) {
				if (right.preOrderSearch(no2) != null) {
					return right.preOrderSearch(no2);
				}
			}
			return null;
		}

		@Override
		public String toString() {
			return "HeroNode [name=" + name + ", no=" + no + "]";
		}
		
		public void preOrder() {
			System.out.println(this);
			if (left != null) {
				left.preOrder();
			}
			if (right != null) {
				right.preOrder();
			}
		}
		
		public void infixOrder() {
			if (left != null) {
				left.infixOrder();
			}
			System.out.println(this);
			if (right != null) {
				right.infixOrder();
			}
		}
		
		public void postOrder() {
			if (left != null) {
				left.postOrder();
			}
			
			if (right != null) {
				right.postOrder();
			}
			
			System.out.println(this);
		}
		
		public HeroNode getLeft() {
			return left;
		}
		public void setLeft(HeroNode left) {
			this.left = left;
		}
		public HeroNode getRight() {
			return right;
		}
		public void setRight(HeroNode right) {
			this.right = right;
		}
	}
}
